package impl.sort;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 19/10/2011
 * Time: 15:11:30
 * To change this template use File | Settings | File Templates.
 */
public class HeapSorter extends AbstractSorter {
    private int size;
    public HeapSorter() {
        super(SorterType.HEAP);
        size = 0;
    }
    public <T> void sort(Comparator<T> c, List<T> list) {
        tree(c, list);
        order(c, list);
    }
    private <T> void tree(Comparator<T> c, List<T> list) {
        size = list.size();
        for(int i=2; i<=size; i++){
            int p = 1;
            while(p!=0){
                if(greater(c, list, (i/p)-1, (i/(2*p))-1)){
                    swap(list, (i/p)-1, (i/(2*p))-1);
                    if((i/(2*p))-1>0){
                        p *= 2;
                    }else{
                        p = 0;
                    }
                }else{
                    p = 0;
                }
            }
        }
    }
    private <T> void order(Comparator<T> c, List<T> list) {
        while(size>1){
            swap(list, 0, size-1);
            size--;
            sink(c, list, 0);
        }
    }
    private <T> void sink(Comparator<T> c, List<T> list, int k) {
        while(2*(k+1)<=size){
            int j = (2*(k+1))-1;
            if(j<size-1 && greater(c, list, j+1, j)){
                j++;
            }
            if(greater(c, list, k, j)){
                break;
            }
            swap(list, k, j);
            k = j;
        }
    }
}